// /**
//  * @param {number[]} candidates
//  * @param {number} target
//  * @return {number[][]}
//  */
// var combinationSum = function (candidates, target) {
//   const ans = [],
//     length = candidates.length
//   // target: 每根递归线中 target减去递归元素的值
//   // combine: 解集
//   // index: 递归的元素
//   const dfs = (target, combine, index) => {
//     // console.log("11", combine)

//     // 数组遍历结束
//     if (index === candidates.length) {
//       return
//     }
//     // 如果等于0，说明获得了正确的答案，把答案推了之后退出递归。
//     if (target === 0) {
//       ans.push(combine)
//       return
//     }
//     // 递归元素值，相当于遍历了传入数组，再dfs
//     dfs(target, combine, index + 1)
//     // 如果大于等于0，说明target还能进行递归，继续冲进去！
//     if (target - candidates[index] >= 0) {
//       console.log("index,", index)
//       dfs(target - candidates[index], [...combine, candidates[index]], index)
//     }
//   }
//   // 传入递归，最开始的递归传初始值
//   dfs(target, [], 0)
//   // for (let i = 0; i < length; i++) {
//   //   console.log(i)
//   //   dfs(target, [], i)
//   // }
//   return ans
// }

var combinationSum = function (candidates, target) {
  let n = candidates.length
  let res = []
  let tmpPath = []
  candidates = candidates.sort((a, b) => {
    return a - b
  })
  let backtrack = (tmpPath, target, start) => {
    if (target == 0) {
      res.push(tmpPath)
      return
    }
    for (let i = start; i < n; i++) {
      if (target < candidates[i]) break
      // tmpPath.push(candidates[i]);
      // backtrack(tmpPath.slice(),target - candidates[i],i);
      // tmpPath.pop();
      // backtrack(tmpPath.concat(candidates[i]), target - candidates[i], i)

      backtrack([...tmpPath, candidates[i]], target - candidates[i], i)
    }
  }
  backtrack(tmpPath, target, 0)
  return res
}

let candidates = [2, 3, 6, 7],
  target = 7
console.log(combinationSum(candidates, target))
